#include <stdio.h>



int max_sub(int arr[], int low, int high)
{
  int sum = 0;
  int current_sum=0, csum = 0;
  int mid = (low+high)/2;
  int i;

  if(low == high) //base cases
    return arr[low] >0 ? arr[low] : 0;
  for(i = mid; i>= low; --i){
    sum += arr[i];
    if(sum > csum)
      csum = sum;
  }
  sum = 0;
  for(i = mid+1; i<=high; ++i){
    sum += arr[i];
    if(sum >current_sum)
      current_sum = sum;
  }
  current_sum += csum;
  sum = 0;

  if(sum < current_sum)
    sum = current_sum; 


  current_sum = max_sub(arr, low, mid);
  if(sum < current_sum)
    sum = current_sum;

  current_sum = max_sub(arr, mid+1, high);
  if(sum < current_sum)
    sum = current_sum;

  return sum;
}

int main()
{
  int arr[] = {31,-41,59,26,-53,58,97,-93,-23,84};
  int i, maxsum;
  for(i = 0; i<10; ++i)
    printf("%d\t",arr[i]);
  puts("");

  maxsum = max_sub(arr,0,9);

  printf("The maximum sub is %d\n", maxsum);
 
  
  return 0;
}
